package krypto.exercise;

import java.math.BigInteger;
import java.util.Random;

public class MillerRabin {

	static final String MAYBE_PRIME = "Maybe prime";
	static final String DEFINETELY_COMPOSITE = "Definetely composite";

	public static BigInteger MakeRandomBigInteger (BigInteger n) {
		//Generate a random value between 2 and (n-1)
		Random rand = new Random();
		BigInteger x = null;
		boolean loop = true;

		while (loop) {
			loop = true;
			x = new BigInteger((n.bitLength()), rand);

			//compareTo returns -1, 0 or 1 as this BigInteger is numerically less than, equal to, or greater than val.
			if ( (x.compareTo(n.subtract(BigInteger.ONE)) <= 0) && (x.compareTo(BigInteger.valueOf(1)) > 0 ) ) {
				loop = false;					
			}	
		}

		return x;
	}

	public static String calcInefficient (BigInteger n) throws Exception {
		//Test 1
		if ( n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(0)) == 0 ) {
			System.out.println("calcInefficient - Test 1");
			return DEFINETELY_COMPOSITE;
		}

		//Test 2

		//Generate a random value between 2 and (n-1)
		BigInteger x = MakeRandomBigInteger(n);

		System.out.println("calcInefficient - Random value x=" + x);

		EEResultBigInteger eEResultBigInteger = EEuclid.calc(n,x);

		if (eEResultBigInteger.L.compareTo(BigInteger.valueOf(1)) != 0) {
			System.out.println("calcInefficient - Test 2");
			return DEFINETELY_COMPOSITE;
		}

		//Test 3
		BigInteger m = n.subtract(BigInteger.valueOf(1));

		BigInteger y = x.modPow(m,n);
		if (y.compareTo(BigInteger.valueOf(1)) != 0) {
			System.out.println("calcInefficient - Test 3");
			return DEFINETELY_COMPOSITE;
		}

		//Test 4
		while ((m.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(0)) == 0) && (y.compareTo(BigInteger.valueOf(1)) == 0)) {
			m = m.divide(BigInteger.valueOf(2));
			y = x.modPow(m,n);

			if ((y.compareTo(BigInteger.valueOf(1)) == 0) || (y.compareTo(n.subtract(BigInteger.valueOf(1))) == 0)) {
				//continue
			} else {
				System.out.println("calcInefficient - Test 4");
				return DEFINETELY_COMPOSITE;
			}
		}

		return MAYBE_PRIME;
	}

	public static String calcEfficient (BigInteger n) throws Exception {

		//Test 1
		if ( n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(0)) == 0 ) {
			System.out.println("calcEfficient - Test 1");
			return DEFINETELY_COMPOSITE;
		}

		//Test 2

		//Generate a random value between 2 and (n-1)
		BigInteger x = MakeRandomBigInteger(n);

		System.out.println("calcEfficient - Random value x=" + x);

		EEResultBigInteger eEResultBigInteger = EEuclid.calc(n,x);

		if (eEResultBigInteger.L.compareTo(BigInteger.valueOf(1)) != 0) {
			System.out.println("calcEfficient - Test 2");
			return DEFINETELY_COMPOSITE;
		}

		//Express (n-1) as m*2^t 
		BigInteger t = BigInteger.ZERO;
		BigInteger m = n.subtract(BigInteger.ONE);

		while (m.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
			t = t.add(BigInteger.ONE);
			m = m.shiftRight(1);
		}	

		System.out.println("calcEfficient - (n-1) expressed as " + m + "*2^" + t);

		BigInteger y;
		y = x.modPow(m,n);

		if ((y.compareTo(BigInteger.valueOf(1)) == 0) || (y.compareTo(n.subtract(BigInteger.valueOf(-1))) == 0)) {
			System.out.println("calcEfficient - Test 3");
			return MAYBE_PRIME;
		}

		BigInteger i = BigInteger.ONE;

		do {
			y = y.modPow(BigInteger.valueOf(2),n);
			if (y.compareTo(n.subtract(BigInteger.valueOf(-1))) == 0) {
				System.out.println("calcEfficient - Test 4");
				return MAYBE_PRIME;
			}

			i = i.add(BigInteger.ONE);
		} while ( i.compareTo(t) <= 0 );

		if (y.compareTo(BigInteger.ONE) != 0) {
			System.out.println("calcEfficient - Test 5" + " " + y + " " + t);
			return DEFINETELY_COMPOSITE;
		}

		return MAYBE_PRIME;
	}


	public static void main(String[] args) throws Exception {
		BigInteger n;

		n = new BigInteger("899809343");
		n = new BigInteger("73");

		//Number of iterations to do Miller-Rabin test.
		int iterations = 15;
//iterations = 2;

		String o1,o2,r1,r2;

		int SameResultCounter = 0;
		int NotSameResultCounter = 0;
		int PrimeCounter = 0;
		int CompositeCounter = 0;

		n = BigInteger.ONE;
		
		//Carmichael number = 561 
		n = BigInteger.valueOf(560);
		
		for (int j = 1; j <= 2; j++) {
 
			n = n.add(BigInteger.ONE);
		

			r1 = MAYBE_PRIME;
			r2 = MAYBE_PRIME;

			for (int i = 1; i < iterations ; i++) {
				o1 = MillerRabin.calcEfficient(n);
				System.out.println("Miller-Rabin Efficient:   input=" + n + " Output=" + o1);

				if (o1.equals(DEFINETELY_COMPOSITE)) {
					r1 = DEFINETELY_COMPOSITE;
				}

				o2 = MillerRabin.calcInefficient(n);
				System.out.println("Miller-Rabin Inefficient: input=" + n + " Output=" + o2);

				if (o2.equals(DEFINETELY_COMPOSITE)) {
					r2 = DEFINETELY_COMPOSITE;
				}
			}

			if ( r1.equals(r2) ) {
				SameResultCounter++;

				if (r1.equals(DEFINETELY_COMPOSITE)) {
					CompositeCounter++;
				} else {
					PrimeCounter++;
				}
			} else {
				NotSameResultCounter++;
			}
		}

		System.out.println("SameResultCounter=" + SameResultCounter + " - NotSameResultCounter=" + NotSameResultCounter);
		System.out.println("CompositeCounter=" + CompositeCounter + " - (Maybe) PrimeCounter=" + PrimeCounter);
	}
}
